package deom1;

import java.util.List;

public class Test1 {

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val; this.next = next;
    }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode ret = head;
        int count = 0;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        count /= 2;
        ret = head;
        while (count != 0) {
            ret = ret.next;
            count--;
        }
        return ret;
    }
}

class Solution1 {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null || fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

class Solution2 {
    public int kthToLast(ListNode head, int k) {
        int count = 0;
        ListNode ret = head;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        count = count - k;
        ret = head;
        while (count != 0) {
            ret = ret.next;
            count--;
        }
        return ret.val;
    }
}
class Solution3 {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        int count = k - 1;
        while (count != 0) {
            fast = fast.next;
            count--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}
class Solution4 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ret = new ListNode(0);
        ListNode head = ret;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                ret.next = list1;
                ret = ret.next;
                list1 = list1.next;
            } else {
                ret.next = list2;
                ret = ret.next;
                list2 = list2.next;
            }
        }
        if (list1 == null) {
            ret.next = list2;
        }
        if (list2 == null) {
            ret.next = list1;
        }
        return head.next;
    }
}